package com.leetcode.partition1;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/9 9:25
 */
public class LC96不同的二叉搜索树 {

    public static int numTrees(int n) {
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
        System.out.println(numTrees(10));
    }

    /**
     * n=1时，有1种；n=2时，有2种；n=3时有5种，而对于n=3，总数等于分别以1、2、3为根结点的二叉搜索树种类和
     * 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
     * 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
     * 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
     * dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
     * dp[i] += dp[j - 1] * dp[i - j]：j - 1表示以j为头结点左子树的结点数量；i - j表示以j为头结点右子树结点数量
     */
    private static int dynamicProgramming(int n) {
        int[] dp = new int[n + 1];      //dp[i]代表以1到i为根结点的二叉搜索树数量
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {      //遍历从1到j分别为根结点的二叉搜索树数量
                dp[i] += dp[j - 1] * dp[i - j];     //dp[j - 1]代表以j为根结点左子树的数量，dp[i - j]代表以j为根结点的右子树的数量
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}
